Bellman-Ford in Almost-Linear Time
September 30, 2026 (GHC 6501 - presented in partial fulfillment of the CSD speaking skills requirement)
In this talk we consider a new algorithm for the single-source shortest paths problem on a directed graph with real-valued (possibly negative) edge weights and solve this problem in m1+o(1) time.
This improves the classic Bellman-Ford algorithm taught in undergraduate courses, which runs in O(mn) time.